package main

import (
	"encoding/json"
	"fmt"
	"sort"
)

func main() {
	points := [][]int{}
	_ = json.Unmarshal([]byte("[[10,16],[2,8],[1,6],[7,12]]"), &points)
	v := findMinArrowShots(points)
	fmt.Println(v)
}

// 452. 用最少数量的箭引爆气球https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons
// 做出来了 但是不知道为什么
func findMinArrowShots(points [][]int) int {
	// 递增排序
	sort.Slice(points, func(i, j int) bool {
		return points[i][0] < points[j][0]
	})

	ans := 0
	//定义箭的影响范围
	var pre []int
	for _, v := range points {
		if pre == nil {
			pre = v
			continue
		}

		// 如果没有重叠，之前的需要一支箭
		if v[0] > pre[1] {
			ans++
			pre = v
			continue
		}

		// 如果有重叠取最小范围
		pre[0] = max(pre[0], v[1])
		pre[1] = min(pre[1], v[1])
	}
	// 最后一个也需要射一只箭
	return ans + 1
}

// 202 快乐数 https://leetcode.cn/problems/happy-number
// 快慢指针这个算法太牛逼了
// todo 需要重做
func isHappy(n int) bool {
	fast := n
	slow := n
	for {
		fast = isHappySub(fast)
		fast = isHappySub(fast)
		slow = isHappySub(slow)
		if fast == slow {
			break
		}
	}
	return fast == 1
}

func isHappySub(n int) int {
	ans := 0
	for n != 0 {
		x := n % 10
		ans += x * x
		n = n / 10
	}
	return ans
}

// 57. 插入区间 https://leetcode.cn/problems/insert-interval/
// todo 需要重做
func insert(intervals [][]int, newInterval []int) [][]int {
	res := [][]int{}
	done := false
	for _, group := range intervals {
		// 新区间在原本元素之外 且还没加进去
		if group[0] > newInterval[1] && !done {
			res = append(res, newInterval, group)
			done = true
			continue
		}
		// 如果新区间已经加进去了，后续的不用考虑了
		// 如果还没加进去，且没遇到重合的，也先把原元素加进去
		if done || group[1] < newInterval[0] {
			res = append(res, group)
			continue
		}
		// 新区间在老区间中
		if group[0] <= newInterval[0] && group[1] >= newInterval[1] {
			res = append(res, group)
			done = true
			continue
		}

		// 新旧有重叠，就把原本的区间加到新区间 继续
		if (newInterval[0] <= group[1] && newInterval[1] >= group[1]) ||
			(newInterval[0] <= group[0] && newInterval[1] >= group[0]) {
			newInterval[0] = min(newInterval[0], group[0])
			newInterval[1] = max(newInterval[1], group[1])
		}
	}
	if !done {
		res = append(res, newInterval)
	}
	return res
}

func mainMerge() {
	var intervals = [][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}}

	res := merge(intervals)
	fmt.Println(res)
}

func merge(intervals [][]int) [][]int {

	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	pre := intervals[0]
	res := [][]int{}
	start := pre[0]
	for i := 1; i < len(intervals); i++ {
		item := intervals[i]
		// 与上一个不是相同区间
		if item[0] > pre[1] {
			res = append(res, []int{start, pre[1]})
			start = item[0]
		}
		pre = item
	}
	res = append(res, []int{start, pre[1]})
	return res
}

func max(v1, v2 int) int {
	if v1 > v2 {
		return v1
	}
	return v2
}
func min(v1, v2 int) int {
	if v1 > v2 {
		return v2
	}
	return v1
}
